/**
 * 插入排序
 * 时间复杂度：
 * 最坏情况数组逆序 O(n^2)
 * 最好情况数组顺序 O(n)
 * 所以如果数据基本有序，用插入排序最好
 * 空间复杂度：O(1)
 * 稳定性：稳定 （一个稳定的排序可以写成不稳定，反之则不行）
 */
public class Sort {
    public void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;         // 4
            for (; j >= 0; j--) {//1 2 3  8
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度：O(n^1.3~1.5);
     * 空间复杂度：O(1);
     * 稳定性：不稳定
     * 适合无序，考的很少
     */
    public void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
    }

    /**
     * 选择排序
     * 时间复杂度O(n^2)，不管是有序无序，都是这样
     * 稳定性：不稳定
     */
    public void choose(int[] array) {
/*        for(int i = 0; i < array.length; i++){
            int tmp = array[i];
            for(int j = i + 1; j < array.length; j++){
                if(tmp > array[j]){
                    tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
            array[i] = tmp;
        }*/
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

    /**
     * 堆排序
     * 时间复杂度O(nlogn)
     */
    public void heapSort(int[] array) {
        createHeap(array);
        int end = array.length - 1;
        while (end >= 0) {
            swap(array, 0, end);
            adjustmentDown(array, 0, end);
            end--;
        }
    }

    //创建堆
    public void createHeap(int[] array) {
        int len = array.length;
        for (int parent = (len - 1 - 1) / 2; parent >= 0; parent--) {
            adjustmentDown(array, parent, len);
        }
    }

    public void adjustmentDown(int[] array, int parent, int len) {
        int child = parent * 2 + 1;

        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[parent] < array[child]) {
                swap(array, child, parent);
                parent = child;
                child = child * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     * 冒泡排序
     * 时间复杂度：O(n^2);
     */
    public void bubble(int[] array){
        for(int i = 0; i < array.length; i++){
            boolean flag = false;
            for(int j = 0; j < array.length - 1 - i; j++){
                if(array[j] > array[j + 1]){
                    swap(array, j, j+1);
                    flag = true;
                }
            }
            if(!flag){
                break;
            }
        }
    }
    /**
     * Hoare法
     * 快速排序
     * 时间复杂度O(nlogn);
     */
    public int fundPivotHoare(int[] array, int start, int end){
        int i = start;//事先存好start下标
        int key = array[start];
        while(start < end){
            //需要继续判断start，循环的同时有可能，左边的数据都比key大
            //取等号的原因是防止死循环(array[start] == array[end])
            while(start < end && key <= array[end]){
                end--;
            }
            while(start < end && key >= array[start]){
                start++;
            }
            swap(array, start, end);
        }
        swap(array,i,start);
        return start; //此时start的左边都比array[start]小，右边都比他大，拿到基准返回
    }

    /**
     * 挖坑法
     * @return start的左边都比array[start]小，右边都比他大，拿到基准返回
     */
    public int fundPivotHole(int[] array, int start, int end){
        int key = array[start];
        while(start < end){
            while(start < end && key <= array[end]){
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }
    public void quick(int[] array, int left, int right){
        if(left >= right){
            return;
        }
        int pivot =fundPivotHole(array, left, right);
        quick(array, left, pivot - 1);
        quick(array,pivot + 1, right);
    }
    public void quickSort(int[] array){
        quick(array, 0,array.length - 1);
    }
}














